#define _CRT_SECURE_NO_WARNINGS 1
// my
class all
{
public:
    int startTime;
    int endTime;
    int profit;

    all() {}

    all(const int s, const int e, const int p)
        :startTime(s), endTime(e), profit(p) {}
};
bool Compare(const all& a1, const all& a2) {
    return a1.endTime < a2.endTime;
}
class Solution {
public:

    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size(), ret = 0;
        vector<all> time(n);
        for (int i = 0; i < n; i++) time[i] = all(startTime[i], endTime[i], profit[i]);
        sort(time.begin(), time.end(), Compare);
        for (int i = 1; i < n; i++)
        {
            int maxcur = time[i].profit;
            for (int j = i - 1; j >= 0; j--)
            {
                if (time[j].endTime <= time[i].startTime)
                {
                    maxcur = time[j].profit + time[i].profit;
                    break;
                }
            }
            if (time[i - 1].profit < maxcur) time[i].profit = maxcur;
            else time[i] = time[i - 1];
        }
        return time[n - 1].profit;
    }
};

// learn
class Solution {
public:

    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size(), ret = 0;
        vector<vector<int>> time(n);
        for (int i = 0; i < n; i++) time[i] = { startTime[i], endTime[i], profit[i] };
        sort(time.begin(), time.end(), [](const vector<int>& v1, const vector<int>& v2) { return v1[1] < v2[1]; });
        vector<int> dp(n);
        dp[0] = time[0][2];
        for (int i = 1; i < n; i++)
        {
            int left = 0, right = i - 1;
            while (left < right) {
                int mid = (left + right + 1) / 2;
                if (time[i][0] < time[mid][1]) right = mid - 1;
                else left = mid;
            }
            if (left == 0 && time[i][0] < time[0][1]) dp[i] = max(dp[i - 1], time[i][2]);
            else dp[i] = max(dp[i - 1], dp[left] + time[i][2]);
        }
        return dp[n - 1];
    }
};